package dp;

import org.junit.Test;

import java.util.Arrays;

public class HouseRobberII213 {

    @Test
    public void test() {
        rob198(new int[]{1, 2, 3, 1});
        rob198(new int[]{2, 7, 9, 3, 1});

        rob213(new int[]{2, 3, 2});
        rob213(new int[]{1, 2, 3, 1});
        rob213(new int[]{0});
    }

    // https://leetcode-cn.com/problems/house-robber/
    public int rob198(int[] n) {
        int r = rob0(n, 0, n.length-1);
        System.out.format("nums: %s, result: %d\n", Arrays.toString(n), r);
        return r;
    }

    public int rob0(int[] n, int start, int end) {
        if (end == start) {
            return n[start];
        }
        int[] dp = new int[end-start+1];
        Arrays.fill(dp, 0);
        for (int i = 0; i < dp.length; i++) {
            if (i == 0 || i == 1) {
                dp[i] = n[i+start];
            } else {
                dp[i] = dp[i-2] + n[i+start];
                if (i >= 3) {
                    dp[i] = Math.max(dp[i], dp[i-3] + n[i+start]);
                }
            }
        }
        return Math.max(dp[dp.length-1], dp[dp.length-2]);
    }

    // 环形分成两部分即可: [0, N-2], [1, N-1]
    public int rob213(int[] n) {
        if (n.length == 1) {
            return n[0];
        }
        int r1 = rob0(n, 0, n.length-2);
        int r2 = rob0(n, 1, n.length-1);
        int r = Math.max(r1, r2);
        System.out.format("nums: %s, result: %d\n", Arrays.toString(n), r);
        return r;
    }
}
